/*
 * @Author: szx
 * @Date: 2022-03-18 13:34:18
 * @LastEditTime: 2022-03-18 13:59:46
 * @Description:
 * @FilePath: \leetcode\剑指offer\13\13.js
 */
/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var movingCount = function (m, n, k) {
    const flag = Array.from(new Array(m), () => {
        return new Array(n).fill(false);
    });
    const dfs = (i, j) => {
        if (i >= m || j >= n || flag[i][j]) return 0;
        let tmp = (i % 10) + Math.floor(i / 10) + (j % 10) + Math.floor(j / 10);
        if (tmp <= k) {
            flag[i][j] = true;
            return 1 + dfs(i + 1, j) + dfs(i, j + 1);
        }
        return 0;
    };
    return dfs(0, 0);
};
console.log(movingCount(2, 3, 1));
console.log(movingCount(3, 1, 0));
console.log(movingCount(16, 8, 4));
